/*
 * ROOT.cpp
 *Algorithmus 4.101
 *bilde die Stufenstruktur zu ROOT
 *Quellcode von rcm.c
 *  Created on: 10.07.2013
 *      Author: to
 */
#ifndef NO_HEADERS
# include <stdlib.h>
# include <string.h>
#endif


void ROOTLS(const INT root, const int flags,
            const INT *restrict xadj, const INT *restrict adj,
            signed char *restrict mask,
            INT *restrict ccsize, INT *restrict nlvl,
            INT *restrict last_lvl, INT *restrict ls)
{
    INT i, j;
    INT nbr, node;

    INT lvl_begin, lvl_end; /* C style indices */

    if (flags & RCM_FORTRAN_INDICES) {
        --mask;
        --xadj;
        --adj;
    }

    ASSERT( !mask[root] );
    mask[root] = 1; /* mask root */

    /* init first level */
    *nlvl = 0;
    ls[0] = root;
    lvl_begin = 0;
    lvl_end = 1;
    *ccsize = 1;

    /*
     * lvl_begin is the pointer to the beginning of the current
     * level, and lvl_end-1 points to the end of this level.
     */
    do {
        /*
         * Generate the next level by finding all the non-masked
         * neighbors of all the nodes in the current level.
         */
        for (i = lvl_begin; i < lvl_end; ++i) {
            node = ls[i];
            for (j = xadj[node]; j < xadj[node + 1]; ++j) {
                nbr = adj[j];
                if (!mask[nbr]) {
                    mask[nbr] = 1;
                    ls[*ccsize] = nbr;
                    ++(*ccsize);
                }
            }
        }

        /*
         * Reset lvl_begin and lvl_end to iterate over the now
         * generated next level.
         */
        *last_lvl = lvl_begin;
        lvl_begin = lvl_end;
        lvl_end = *ccsize;
        ++(*nlvl);
    }
    while (lvl_end - lvl_begin > 0);

    /*
     * Reset mask to zero for the nodes in the level structure,
     * i.e. the nodes are again unmasked.
     */
    for (i = 0; i < *ccsize; ++i) {
        mask[ ls[i] ] = 0;
    }

}



